Test de primalidad de Fermat
- Test de primalidad de Fermat
- El pequeño teorema de Fermat enuncia que si p es primo y a es coprimo con p, entonces ap-1 - 1 es divisible por p. Esto también se puede expresar así: ap-1 = 1 (mod p).
Resulta que el recíproco de este teorema suele ser verdad: si p es compuesto, entonces ap-1 es poco probable que sea congruente con 1 módulo p para un valor arbitrario de a.
El programa de cifrado PGP aprovecha esta propiedad del teorema para comprobar si los grandes números aleatorios que elige son primos. Comprueba los valores que llamaremos x utilizando 4 valores de a (llamados testigos) utilizando la fórmula anterior. Estos cuatro valores son 2, 3, 5 y 7, los cuatro primeros números primos. Si 1 = 2x-1 = 3x-1 = 5x-1 = 7x-1 (mod x), entonces sabe que el número x es probablemente primo. Si de alguna de las expresiones anteriores se obtiene un valor distinto de 1, entonces x es definitivamente compuesto. Utilizar un número mayor de testigos disminuye la probabilidad de que un número compuesto x parezca primo, aunque muy pocos números grandes pueden engañar a los cuatro testigos ya mencionados.
Enciclopedia Universal.
2012.
Mira otros diccionarios:
Test de primalidad de Fermat — El pequeño teorema de Fermat enuncia que si p es primo y a es coprimo con p, entonces ap 1 1 es divisible por p. Esto también se puede expresar así: ap 1 = 1 (mod p). Resulta que el recíproco de este teorema suele ser verdad: si p es compuesto,… … Wikipedia Español
Test de primalidad de Miller-Rabin — El Test de primalidad de Miller Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trata de un… … Wikipedia Español
Test de primalidad de Miller-Rabin — El Test de primalidad de Miller Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trata de un… … Enciclopedia Universal
Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n … Wikipedia Español
Test de primalidad AKS — El test de primalidad AKS o algoritmo AKS es un algoritmo determinista que decide en tiempo polinómico si un número natural es primo o compuesto. Fue diseñado por los científicos de computación Manindra Agrawal, Neeraj Kayal y Nitin Saxena del… … Wikipedia Español
Test de Pépin — En matemáticas, el test de Pépin (por el matemático francés P. Pépin) es un test de primalidad que se puede emplear para determinar si un número de Fermat es primo. Es una variante del test de Proth. Contenido 1 Descripción del test 2… … Wikipedia Español
Test de Pocklington — El test de Pocklington es un test de primalidad para cierto conjunto de números inventado por Henry Cabourn Pocklington en 1914.[1] Sea N = fr + 1 donde 0 < r < f+2 y se conocen todos los factores primos de f. El teorema sostiene que N es… … Wikipedia Español
Pequeño teorema de Fermat — Saltar a navegación, búsqueda … Wikipedia Español
Análisis de primalidad AKS — Saltar a navegación, búsqueda El análisis de primalidad AKS o algoritmo AKS es un algoritmo determinista que decide en tiempo polinómico si un número natural es primo o compuesto. Fue diseñado por los científicos de computación Manindra Agrawal,… … Wikipedia Español
Aritmética Modular Compleja — Saltar a navegación, búsqueda La ‘Aritmética Modular Compleja’ (hacia un nuevo test de primalidad) Contenido 1 La ‘Aritmética Modular Compleja’.La ‘semiarcotangente discreta’ 2 El Indicador imaginario de Euler´: IiE (M) … Wikipedia Español
